package com.lenl.arithmetic.search;

/**
 * @author Lenl
 * @version v1.0
 * @create 2022-05-02 16:53
 * @description 插值寻找算法,适用于查找值分布比较均匀的情况下更好，否则二分可能更好
 */
public class InsertValueSearch {
    public static void main(String[] args) {
        int[] arr=new int[100];
        for (int i=0;i<100;i++){
            arr[i]=i+1;
        }
        int res=doInsertValueSearch(arr,0,arr.length-1,1);

        System.out.println("res="+res);
    }

    private static int doInsertValueSearch(int[] arr,int left,int right,int findVal){
        //条件必须有，否则可能越界
        if(left>right||findVal<arr[0]||findVal>arr[arr.length-1]){
            return -1;
        }
        //求出mid
        int mid=left+(right-left)*(findVal-arr[left])/(arr[right]-arr[left]);
        int midVal=arr[mid];
        if(findVal>midVal){
            //说明应该向右递归查找
            return doInsertValueSearch(arr,mid+1,right,findVal);
        }else if(findVal<midVal){
            //说明向左递归查找
            return doInsertValueSearch(arr,left,mid-1,findVal);
        }else{
            return mid;
        }

    }
}
